#ifndef _BINARYLINKTREE_H_
#define _BINARYLINKTREE_H_

#include <iostream>

#define ElementType void*

template <typename T>
class BinaryLinkTree
{
public:
    BinaryLinkTree();
    ~BinaryLinkTree();

    void Insert(T element);
    void Remove(T element);
    T* Find(T element);
    T* FindByIndex(int index);

    void show();

    void SetCallbackCompareID(int (*CompareIDPtr)(T, T));
    void SetCallbackShowElement(void (*ShowElement)(T));
    void SetCallbackSearchByIndex(int (*SearchIDPtr)(T, int));

private:
    struct Node
    {
        Node(T element)
            : data(element), left(nullptr), right(nullptr), parent(nullptr) {}

        T data;
        Node *left;
        Node *right;
        Node *parent;
    };

    void PrevTravel(Node *node);
    void MidTravel(Node *node);
    void PostTravel(Node *node);

    Node* InsertNode(Node *node, T element);
    int GetNodeHeight(Node* node);
    int LeftRightDeviation(Node *node);

    T* FindNode(Node* node, T element);
    T* FindNodeByIndex(Node *node, int index);

    Node* RemoveNode(Node *node, T element);
    Node* GetMinNode(Node* node);

    Node* RotateLeft(Node *node);
    Node* RotateRight(Node *node);
    Node* RotateLeftRight(Node *node);
    Node* RotateRightLeft(Node *node);

    Node *root;

    int (*CompareID)(T, T);
    void (*ShowElement)(T);
    int (*SearchIDByIndex)(T,int);
};

template <typename T>
BinaryLinkTree<T>::BinaryLinkTree() : root(nullptr) {}

template <typename T>
BinaryLinkTree<T>::~BinaryLinkTree() {}

template <typename T>
void BinaryLinkTree<T>::Insert(T data) 
{
    root = InsertNode(root, data);
}

template <typename T>
void BinaryLinkTree<T>::Remove(T element) 
{
    root = RemoveNode(root, element);
}

template <typename T>
T* BinaryLinkTree<T>::Find(T element) 
{
    return FindNode(root, element);
}

template <typename T>
T* BinaryLinkTree<T>::FindByIndex(int index) 
{
    return FindNodeByIndex(root, index);
}

template <typename T>
void BinaryLinkTree<T>::show() 
{
    PrevTravel(root);
    std::cout << std::endl;
    MidTravel(root);
    std::cout << std::endl;
    PostTravel(root);
    std::cout << std::endl;
}

template <typename T>
void BinaryLinkTree<T>::SetCallbackCompareID(int (*CompareIDPtr)(T, T)) 
{
    CompareID = CompareIDPtr;
}

template <typename T>
void BinaryLinkTree<T>::SetCallbackShowElement(void (*ShowElement)(T)) 
{
    this->ShowElement = ShowElement;
}

template <typename T>
void BinaryLinkTree<T>::SetCallbackSearchByIndex(int (*SearchIDPtr)(T, int)) 
{
    SearchIDByIndex = SearchIDPtr;
}

template <typename T>
void BinaryLinkTree<T>::PrevTravel(Node *node) 
{
    if (node == nullptr) return;
    ShowElement(node->data);
    PrevTravel(node->left);
    PrevTravel(node->right);
}

template <typename T>
void BinaryLinkTree<T>::MidTravel(Node *node) 
{
    if (node == nullptr) return;
    MidTravel(node->left);
    ShowElement(node->data);
    MidTravel(node->right);
}

template <typename T>
void BinaryLinkTree<T>::PostTravel(Node *node) 
{
    if (node == nullptr) return;
    PostTravel(node->left);
    PostTravel(node->right);
    ShowElement(node->data);
}

template <typename T>
typename BinaryLinkTree<T>::Node* BinaryLinkTree<T>::InsertNode(Node* node, T data) 
{
    if (node == nullptr)
        return new Node(data);

    if (CompareID(node->data, data) == 0)
        return node;

    if (CompareID(node->data, data) > 0) {
        node->left = InsertNode(node->left, data);
        if (LeftRightDeviation(node) > 1) {
            if (CompareID(node->left->data, data) > 0)
                node = RotateRight(node);
            else
                node = RotateLeftRight(node);
        }
    } else {
        node->right = InsertNode(node->right, data);
        if (LeftRightDeviation(node) < -1) {
            if (CompareID(node->right->data, data) > 0)
                node = RotateRightLeft(node);
            else
                node = RotateLeft(node);
        }
    }

    return node;
}

template <typename T>
int BinaryLinkTree<T>::GetNodeHeight(Node *node) 
{
    if (node == nullptr)
        return 0;
    int lh = GetNodeHeight(node->left);
    int rh = GetNodeHeight(node->right);
    return (lh > rh ? lh : rh) + 1;
}

template <typename T>
int BinaryLinkTree<T>::LeftRightDeviation(Node *node) 
{
    return GetNodeHeight(node->left) - GetNodeHeight(node->right);
}

template <typename T>
T* BinaryLinkTree<T>::FindNode(Node *node, T data) 
{
    if (node == nullptr)
        return nullptr;

    if (CompareID(node->data, data) == 0)
        return &node->data;
    else if (CompareID(node->data, data) > 0)
        return FindNode(node->left, data);
    else
        return FindNode(node->right, data);
}

template <typename T>
T* BinaryLinkTree<T>::FindNodeByIndex(Node *node, int index) 
{
    if (node == nullptr)
        return nullptr;

    if (SearchIDByIndex(node->data, index) == 0)
        return &node->data;
    else if (SearchIDByIndex(node->data, index) > 0)
        return FindNodeByIndex(node->left, index);
    else
        return FindNodeByIndex(node->right, index);
}

template <typename T>
typename BinaryLinkTree<T>::Node* BinaryLinkTree<T>::RemoveNode(Node *node, T element) 
{
    if (node == nullptr)
        return node;

    if (CompareID(node->data, element) > 0)
        node->left = RemoveNode(node->left, element);
    else if (CompareID(node->data, element) < 0)
        node->right = RemoveNode(node->right, element);
    else {
        if (node->left == nullptr || node->right == nullptr) {
            Node *temp = node->left ? node->left : node->right;
            if (temp == nullptr) {
                delete node;
                node = nullptr;
            } else {
                temp->parent = node->parent;
                delete node;
                node = temp;
            }
        } else {
            Node *min = GetMinNode(node->right);
            node->data = min->data;
            node->right = RemoveNode(node->right, min->data);
        }
    }

    if (node == nullptr)
        return node;

    if (LeftRightDeviation(node) > 1) {
        if (LeftRightDeviation(node->left) > 0)
            node = RotateRight(node);
        else
            node = RotateLeftRight(node);
    } else if (LeftRightDeviation(node) < -1) {
        if (LeftRightDeviation(node->right) > 0)
            node = RotateRightLeft(node);
        else
            node = RotateLeft(node);
    }

    return node;
}

template <typename T>
typename BinaryLinkTree<T>::Node* BinaryLinkTree<T>::GetMinNode(Node *node) 
{
    Node *min = node;
    while (min->left != nullptr)
        min = min->left;
    return min;
}

template <typename T>
typename BinaryLinkTree<T>::Node* BinaryLinkTree<T>::RotateLeft(Node *node) 
{
    Node *t = node->right;
    node->right = t->left;
    t->left = node;
    t->parent = node->parent;
    node->parent = t;
    return t;
}

template <typename T>
typename BinaryLinkTree<T>::Node* BinaryLinkTree<T>::RotateRight(Node *node) 
{
    Node *t = node->left;
    node->left = t->right;
    t->right = node;
    t->parent = node->parent;
    node->parent = t;
    return t;
}

template <typename T>
typename BinaryLinkTree<T>::Node* BinaryLinkTree<T>::RotateLeftRight(Node *node) 
{
    node->left = RotateLeft(node->left);
    return RotateRight(node);
}

template <typename T>
typename BinaryLinkTree<T>::Node* BinaryLinkTree<T>::RotateRightLeft(Node *node) 
{
    node->right = RotateRight(node->right);
    return RotateLeft(node);
}

#endif